package com.itcast.demo.tokkit;

import com.itcast.demo.entity.ListNode;

/**
 * @author zheng.zhang
 */
public class LinkedTest {

    /**
     * 判断给定的链表中是否有环。如果有环则返回true，否则返回false。
     *
     * @param head 头结点
     * @return 是否有环
     */
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        // 快指针
        ListNode fastNode = head;
        // 慢指针
        ListNode slowNode = head;
        while (fastNode != null && fastNode.next != null) {
            // 快指针走两步
            fastNode = fastNode.next.next;
            // 慢指针走一步
            slowNode = slowNode.next;
            // 如果快慢指针相遇,则说明有环
            if (fastNode == slowNode) {
                return true;
            }
        }
        return false;
    }
}
